最近屈哥布置的USACO的月赛题，难度不是太大，但是T2的一些小细节还是没太想清楚，看了下题解

注：为了优化阅读体验，代码统一放到了文章末尾处

YALIOJ Link

Balance Beam

Luogu P5155

Description

给定一个长为nn的序列，可以选择以12\frac{1}{2}的概率进行左右移动，也可以结束并得到当前位置上的收益fif_i（fif_i给出）

求从每个位置开始时使用最优策略的最大期望收益是多少

Constraints

n≤105n\leq 10^5

Solution

一看到12\frac{1}{2}的概率随机游走就自然而然地想到了赌徒破产模型

显然，以ii开始的答案，要么是直接在ii结束，要么是往左/右随机游走到一个收益尽可能大的点并停下

假设往左走到xx点，往右走到yy点，那么它们对以ii位置开始的答案贡献即为y−iy−xfx+i−xy−xfy\frac{y-i}{y-x}f_x + \frac{i-x}{y-x}f_y，我们就是要找到点对(x,y)(x,y)使得这个东西最大

这个贡献的式子很优美，稍微观察一下就会发现它就是在坐标系中(x,fx)(x, f_x)，(y,fy)(y, f_y)这两点的连线与直线x=ix=i的焦点的纵坐标

我们要使得交点纵坐标尽量大，那么显然只需要维护一个上凸壳即可（真的很显然，我连图都懒得放了）

Sort It Out

Luogu P5156

Description

给定一个长为nn的排列，可以选择一个集合SS，不断重复比较SS内的每个元素与原排列相邻元素的大小关系，若相邻元素不递增则交换。

你需要选择一个集合SS使得操作后排列变为上升序列

求满足这样条件的，且集合大小最小的集合中字典序第kk小的集合

Constraints

n≤105,k≤1018n\le 10^5, k\le 10^{18}

Solution

原题意很绕，首先不难注意到这样一个事实：若操作集合SS后能够将序列排好序，那么SS中的每个元素在最后序列中都会被放到该放的位置上去（元素xx被移动到第xx位），且集合SS以外的元素的相对位置关系不变。因此SS以外的元素就必须是一个单调上升子序列

于是题目就能转化为，求原序列字典序第kk大的最长上升子序列（把原问题对偶）

对于这个问题，我们只需要在树状数组求LIS的时候多记一个以当前点开头的LIS数量，并用一个vector记录一下每一次的转移信息，最后把vector元素从大到小排序，用类似于线段树求第kk大的方法计算一下即可

注意在统计第kk大时，需要保证元素下标单调递增；以及统计次数的时候有可能会爆long long，所以要对101810^{18}取min

具体实现不是很难

The Cow Gathering

Luogu P5157

Description

给定一棵nn个节点的树，有mm个限制(u,v)(u,v)表示uu必须在vv前删除

问每次删除一个叶子节点，可能最后一个留下的点的集合

Constraints

n,m≤105n, m\le 10^5

Solution

这应该是这一场里最傻逼的一道题了

考虑添加一条限制(u,v)(u,v)后对答案集合产生的影响

显然，以vv为根，在uu的子树中的点都不可能最后留下了

于是我们每次把这些点标记一下即可

标记的话，可以直接对以11为根，一段连续的dfs序操作。具体来说，若以11为根时，vv在uu的子树中，则倍增/二分找到vv在uu的哪个儿子的子树中，对这棵子树外的部分修改；否则直接对uu的子树修改

可以用前缀和或者树状数组维护

注意，最后还需要跑一遍拓扑排序特判一下无解的情况

Codes

T1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;
typedef pair <LL, LL> pll;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 1e5 + 100;

int N;
pii A[Maxn];

namespace GEOM
{
	int top, Hull[Maxn];
	pii Stack[Maxn];

	inline LL cross (pii x, pii y, pii z) // 向量 x->y 叉乘向量 x->z
	{
		pii a = mp(y.x - x.x, y.y - x.y), b = mp(z.x - x.x, z.y - x.y);
		return (LL)a.x * b.y - (LL)b.x * a.y;
	}

	inline void get_hull ()
	{
		Stack[++top] = A[0];
		for (int i = 1; i <= N + 1; ++i)
		{
			while (top > 1 && cross (Stack[top - 1], Stack[top], A[i]) >= 0) --top;
			Stack[++top] = A[i];
		}
		for (int i = 1; i <= top; ++i) Hull[i] = Stack[i].x;
	}
}

using namespace GEOM;

inline void Solve ()
{
	get_hull ();

	for (int i = 1; i <= N; ++i)
	{
		int y = lower_bound (Hull + 1, Hull + top + 1, i) - Hull, x = y - 1;
		x = Hull[x], y = Hull[y];

		if (y == i) printf("%lld\n", (LL)A[i].y * 100000);
		else
		{
			long double left = (long double)100000 * A[x].y * (y - i) / (y - x);
			long double right = (long double)100000  * A[y].y * (i - x) / (y - x);
			printf("%lld\n", (LL)(left + right));
		}
	}
}

inline void Input ()
{
	N = read<int>();
	A[0] = mp(0, 0);
	for (int i = 1; i <= N; ++i) A[i] = mp(i, read<int>());
	A[N + 1] = mp(N + 1, 0);
}

int main()
{

#ifdef hk_cnyali
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif

	Input ();
	Solve ();

	return 0;
}

T2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 1e5 + 100;
const LL inf = 1e18;

int N, A[Maxn], Vis[Maxn];
LL K;

struct info
{
	int max;
	LL cnt;
	inline void operator += (const info &rhs)
	{
		if (Chkmax(max, rhs.max)) cnt = rhs.cnt;
		else if (max == rhs.max) cnt = min(inf, cnt + rhs.cnt);
	}
};

namespace BIT
{
#define lowbit(x) (x & (-x))
	info sum[Maxn];
	inline void add (int x, info val) { for (; x; x -= lowbit(x))  sum[x] += val; }
	inline info query (int x) { info ans = (info){0, 1}; for (; x <= N; x += lowbit(x)) ans += sum[x]; return ans; }
}

typedef pair <int, LL> pil;

vector <pil> G[Maxn];

inline int cmp (pil a, pil b) { return A[a.x] > A[b.x]; }

inline void Solve ()
{
	for (int i = N; i >= 1; --i)
	{
		info now = BIT :: query (A[i] + 1);
		++now.max;
		BIT :: add (A[i], now);
		G[now.max].pb(mp(i, now.cnt));
	}

	int ans = BIT :: query (1).max;
	printf("%d\n", N - ans);

	int pos = 0;
	for (int i = ans; i >= 1; --i)
	{
		sort(G[i].begin(), G[i].end(), cmp);
		for (int j = 0; j < G[i].size(); ++j)
		{
			pil now = G[i][j];
			int x = now.x; LL cnt = now.y;
			if (x < pos) continue;
			if (cnt >= K)
			{
				Vis[A[x]] = 1;
				pos = x;
				break;
			}
			K -= cnt;
		}
	}

	for (int i = 1; i <= N; ++i) if (!Vis[i]) printf("%d\n", i);
}

inline void Input ()
{
	N = read<int>(), K = read<LL>();
	for (int i = 1; i <= N; ++i) A[i] = read<int>();
}

int main()
{

#ifdef hk_cnyali
	freopen("B.in", "r", stdin);
	freopen("B.out", "w", stdout);
#endif

	Input ();
	Solve ();

	return 0;
}

T3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
    T sum = 0, fl = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
    for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
    return sum * fl;
}

inline void proc_status ()
{
    ifstream t ("/proc/self/status");
    cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 1e5 + 100;

int N, M, deg[Maxn], Vis[Maxn];
vector <int> G1[Maxn], G2[Maxn];

int anc[20][Maxn], dep[Maxn], dfn[Maxn], dfs_clock, size[Maxn];

inline void dfs (int x)
{
    dfn[x] = ++dfs_clock, size[x] = 1;
    dep[x] = dep[anc[0][x]] + 1;
    for (int i = 1; i <= 17; ++i) anc[i][x] = anc[i - 1][anc[i - 1][x]];

    for (int i = 0; i < G1[x].size(); ++i)
    {
        int y = G1[x][i];
        if (y == anc[0][x]) continue;
        anc[0][y] = x;
        dfs(y);
        size[x] += size[y];
    }
}

inline void Check ()
{
    static queue <int> Q;
    for (int i = 1; i <= N; ++i) if (deg[i] <= 1) Q.push(i), Vis[i] = 1;

    int cnt = 0;
    while (!Q.empty())
    {
        ++cnt;
        int x = Q.front(); Q.pop();
        for (int i = 0; i < G1[x].size(); ++i)
        {
            int y = G1[x][i];
            --deg[y];
            if (!Vis[y] && deg[y] <= 1) Q.push(y), Vis[y] = 1;
        }
        for (int i = 0; i < G2[x].size(); ++i)
        {
            int y = G2[x][i];
            --deg[y];
            if (!Vis[y] && deg[y] <= 1) Q.push(y), Vis[y] = 1;
        }
    }

    if (cnt != N) { for (int i = 1; i <= N; ++i) puts("0"); exit(0); }
}

int Ans[Maxn], ANS[Maxn];

inline void Solve ()
{
    dfs (1);
    for (int i = 1; i <= M; ++i)
    {
        int x = read<int>(), y = read<int>();
        G2[x].pb(y), ++deg[y];

        if (dfn[x] <= dfn[y] && dfn[y] <= dfn[x] + size[x] - 1)
        {
            for (int j = 17; j >= 0; --j) if (dep[anc[j][y]] > dep[x]) y = anc[j][y];
            ++Ans[1], --Ans[dfn[y]];
            ++Ans[dfn[y] + size[y]];
        }
        else
        {
            ++Ans[dfn[x]], --Ans[dfn[x] + size[x]];
        }
    }

    Check ();

    for (int i = 1; i <= N; ++i) Ans[i] += Ans[i - 1];
    for (int i = 1; i <= N; ++i) printf("%d\n", !Ans[dfn[i]]);
}

inline void Input ()
{
    N = read<int>(), M = read<int>();
    for (int i = 1; i < N; ++i)
    {
        int x = read<int>(), y = read<int>();
        G1[x].pb(y), G1[y].pb(x);
        ++deg[x], ++deg[y];
    }
}

int main()
{

#ifdef hk_cnyali
    freopen("C.in", "r", stdin);
    freopen("C.out", "w", stdout);
#endif

    Input ();
    Solve ();

    return 0;
}